Comptage de chaînes (graphe non orienté) - Exemple

Prenons le graphe ci-dessous.

Sa matrice d'adjacence est  \(A=\begin {pmatrix} 0&1&0&0&0\\1&0&1&1&1\\0&1&0&1&0\\0&1&1&0&1\\0&1&0&1&0\end {pmatrix}\)

\(M=A^3=\begin {pmatrix} 0&4&1&2&1\\4&4&6&6&6\\1&6&2&5&2\\2&6&5&4&5\\1&6&2&5&2\end {pmatrix}\)

On lit donc (coefficients  \(m_{1,4}=m_{4,1}\) ) qu'il y a une seule chaîne de 3 arêtes qui relie les sommets 1 et 4 ; il s'agit de la chaîne 1 - 2 - 4 - 3.

On lit aussi (coefficients  \(m_{3,4}=m_{4,3}\) ) qu'il y a cinq chaînes de longueur 3 qui relient les sommets 3 et 4. 

Listons-les ci-dessous :

• 3 - 4 - 3 - 4
• 3 - 2 - 5 - 4
  
• 3 - 4 - 2 - 4
• 3 - 4 - 5 - 4
• 3 - 2 - 3 - 4

Remarques

• Comme le graphe n'est pas orienté, la matrice  \(A\)  et toutes ses puissances sont symétriques.
• Certaines de ces chaînes utilisent plusieurs fois la même arête.